211. Design Add and Search Words Data Structure

1. Question

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

• WordDictionary() Initializes the object.
• void addWord(word) Adds word to the data structure, it can be matched later.
• bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

2. Examples

Example:

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]

Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

3. Constraints

• 1 <= word.length <= 500
• word in addWord consists lower-case English letters.
• word in search consist of '.' or lower-case English letters.
• At most 50000 calls will be made to addWord and search.

4. References

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/design-add-and-search-words-data-structure 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

5. Solutions

难的还是通配符的处理

class WordDictionary {
  private Tire root;

  public WordDictionary() {
    root = new Tire();
  }

  public void addWord(String word) {
    Tire cur = root;
    // 根据单词中的每个字母逐层遍历，最后标记单词存在的地方
    for (int i = 0; i < word.length(); i++) {
      int index = word.charAt(i) - 'a';
      if (cur.children[index] == null) {
        cur.children[index] = new Tire();
      }
      cur = cur.children[index];
    }
    cur.isWord = true;
  }

  public boolean search(String word) {
    return searchSub(word, 0, root);
  }

  public boolean searchSub(String word, int start, Tire node) {
    Tire cur = node;
    for (int i = start; i < word.length(); i++) {
      char c = word.charAt(i);
      // 处理通配符情况
      if (c == '.') {
        for (int j = 0; j < 26; j++) {
          if (cur.children[j] != null && searchSub(word, i + 1, cur.children[j])) {
            return true;
          }
        }
        // 通配下都为null或者isWord均为false
        return false;
      }
      // 处理普通情况
      if (cur.children[c - 'a'] == null) {
        return false;
      }
      cur = cur.children[c - 'a'];
    }
    return cur.isWord;
  }

  // 创建一个字典树
  // 每个对象相当于一个字符，其中数组对应当前字符的下个字符，共26种可能性
  // isWord标记当前遍历到的是否为单词
  class Tire {
    public boolean isWord;
    public Tire[] children;

    public Tire() {
      isWord = false;
      children = new Tire[26];
    }
  }
}

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * boolean param_2 = obj.search(word);
 */